A branch, in a computer program, is a jump or departure from the implicit or declared order in which instructions are being executed. Instruction pre-fetch is a technique which attempts to minimize the time a processor spends waiting for instructions to be fetched from memory. Instructions following the instruction currently being executed are loaded into a pre-fetch queue when the processor's external bus is otherwise idle. If the processor executes a branch instruction or receives an interrupt, then the queue must be flushed and reloaded from the new address.
Branch target prediction is a technique used in some processors with instruction pre-fetch to guess whether a conditional branch will be taken or not and pre-fetch code from the appropriate location. When a branch instruction is executed, its address and that of the next instruction executed (the chosen destination of the branch) are stored in the branch target buffer. This information is used to predict which way the instruction will branch the next time it is executed so that instruction pre-fetch can continue. When the prediction is correct (and it is correct most of the time), executing a branch does not cause a pipeline break. Some later processors simply pre-fetch both paths instead of trying to predict which way the branch will go. A branch target buffer is a register used to store the predicted destination of a branch in a microprocessor using branch prediction. Branch target prediction, however, does not come without its drawbacks.
The PowerPC processor, for example, decodes instructions including branches and classifies the type of each branch prior to making branch prediction. The PowerPC processor utilizes three hardware components to predict branches. The first component is a Branch History Table (BHT) for a conditional branch to predict whether or not the branch will be taken. The second component is a link stack to predict the target address of a branch that is an indirect branch and corresponds to a subroutine return. The third component is a count cache used to predict the target address of a branch that is an indirect branch but does not correspond to a subroutine return.
The prediction accuracy of the BHT and the link stack is very high. But unlike these two structures, the count cache has low prediction accuracy especially for applications written in C++ or Java. When a branch commits, the branch stores its current target address to the entry in the count cache indexed by its hashed program counter. When the same branch is fetched, the branch accesses the count cache with its hashed program counter, and the relevant entry in the count cache returns the stored target. Such a prediction mechanism is vulnerable to a branch that has multiple different target addresses, because it does not keep track of all possible targets but stores only the most recent target. However, because branch prediction has significant design constraints in terms of design complexity and wire delay, it is difficult to implement a sophisticated algorithm to predict the next target address accurately for a hard-to-predict branch (i.e., a multi-target branch).
Therefore, a need exists to overcome the problems with the prior art as discussed above, and particularly for a more efficient way to predict the next target address for multi-target branches in microprocessors.